package com.kingwood.algorithm.zuochengyun.dandiaoduilie;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.PriorityQueue;

// 滑动窗口最大值（单调队列经典用法模版）
// 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧
// 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
// 返回 滑动窗口中的最大值 。
// 测试链接 : https://leetcode.cn/problems/sliding-window-maximum/
public class Code01_SlidingWindowMaximum {

    // 超时
    public static int[] maxSlidingWindow1(int[] arr, int k) {
        int n = arr.length;
        int m = n - k + 1;
        int[] ans = new int[m];
        int ansIndex = 0;
        // 维护队列从大到小顺序
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);

        for (int l = 0, r = 0; r < n; r++) {
            queue.add(arr[r]);

            int len = r - l + 1;
            if (len >= k) {
                // 结算答案
                ans[ansIndex] = queue.peek();
                ansIndex++;

                Integer removed = arr[l];
                for(Integer val : queue){
                    if(val.equals(removed)){
                        queue.remove(val);
                        break;
                    }
                }

                l++;
            }
        }

        return ans;
    }

    // 超时
    public static int[] maxSlidingWindow2(int[] arr, int k) {
        int n = arr.length;
        int curMax = Integer.MIN_VALUE;
        int m = n - k + 1;
        int[] ans = new int[m];
        int ansIndex = 0;

        for (int l = 0, r = 0; r < n; r++) {
            int len = r - l + 1;
            curMax = Math.max(curMax, arr[r]);

            if (len >= k) {
                // 结算答案
                for (int i=l; i<=r; i++) {
                    curMax = Math.max(curMax, arr[i]);
                }

                ans[ansIndex] = curMax;
                ansIndex++;
                l++;
                curMax = Integer.MIN_VALUE;
            }
        }

        return ans;
    }


    public static int MAXN = 100001;

    public static int[] deque = new int[MAXN];

    public static int h, t;

    public static int[] maxSlidingWindow(int[] arr, int k) {
        h = t = 0;
        int n = arr.length;

        // 先形成长度为k-1的窗口
        for (int i = 0; i < k - 1; i++) {
            // 大 -> 小
            while (h < t && arr[deque[t - 1]] <= arr[i]) {
                t--;
            }
            deque[t++] = i;
        }

        int m = n - k + 1;
        int[] ans = new int[m];

        // 当前窗口k-1长度
        for (int l = 0, r = k - 1; l < m; l++, r++) {
            // 少一个，要让r位置的数进来
            while (h < t && arr[deque[t - 1]] <= arr[r]) {
                t--;
            }
            deque[t++] = r;
            // 收集答案
            ans[l] = arr[deque[h]];
            // l位置的数出去
            if (deque[h] == l) {
                h++;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {9,10,9,-7,-4,-8,2,-6};
        int[] res = maxSlidingWindow(nums, 5);
        System.out.println(Arrays.toString(res));

//        // 维护队列从大到小顺序
//        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
//
//        // 尝试插入一些数字，并确保它们是从大到小的顺序
//        queue.offer(10);
//        queue.offer(8);
//        queue.offer(11);
//        queue.offer(7);
//        queue.offer(8);
//
//        Integer removed = 8;
//
//        for(Integer val : queue){
//            if(val.equals(removed)){
//                queue.remove(val);
//                break;
//            }
//        }
//
//        System.out.println(queue.poll());
//        System.out.println(queue.poll());
//        System.out.println(queue.poll());
//        System.out.println(queue.poll());
//
//        int firstMax = Math.max(Integer.MIN_VALUE, 5);
//        System.out.println(firstMax);
//        int secondMax = Math.max(Math.min(firstMax,5), Integer.MIN_VALUE);
//        System.out.println(secondMax);

    }
}
